A "basic block" is a contiguous set of instructions bounded by branches and/or branch targets, containing no branches or branch targets. This implies that if any instruction in a basic block is executed, then all instructions in the basic block will be executed, i.e. the instructions contained within any basic block are executed on an all-or-nothing basis. The instructions within a basic block are enabled for execution when control is passed to the basic block by an earlier branch targeting the basic block ("targeting" as used here includes both explicit targeting via a taken branch as well as implicit targeting via a not taken branch). The foregoing implies that if control is passed to a basic block, then all instructions in the basic block must be executed; if control is not passed to the basic block, then all instructions in the basic block must not be executed. The act of executing, or specifying the execution of, an instruction before control has been passed to the instruction is called "speculation." Speculation performed by the processor at program runtime is called "dynamic speculation" while speculation specified by the compiler is called "static speculation." Dynamic speculation is known in the prior art.
Two instructions are deemed "independent" when one does not require the result of the other; when one instruction does require the result of the other they are termed "dependent" instructions. Independent instructions may be executed in parallel while dependent instructions must be executed in serial fashion. Program performance is improved by identifying independent instructions and executing as many of them in parallel as possible. Experience indicates that more independent instructions can be found by searching across multiple basic blocks than can be found by searching only within individual basic blocks, however, simultaneously executing instructions from multiple basic blocks requires speculation. Identifying and scheduling independent instructions, and thereby increasing performance, is one of the primary tasks of compilers and processors. The trend in compiler and processor design has been to increase the scope of the search for independent instructions in each successive generation. In prior art instruction sets, an instruction that may generate an exception cannot be speculated by the compiler since, if the instruction causes an exception, the program may erroneously generate an exception when the program should not have. This restricts the useful scope of the compiler's search for independent instructions and makes it necessary for speculation to be performed at program runtime by the processor via dynamic speculation. However, dynamic speculation entails a significant amount of hardware complexity, furthermore, the complexity increases exponentially with the number of basic blocks over which dynamic speculation is applied--this places a practical limit on the scope of dynamic speculation. By contrast, the scope over which the compiler can search for independent instructions is much larger--potentially the entire program. Furthermore, once the compiler has been designed to perform static speculation across a single basic block boundary, very little additional complexity is incurred by statically speculating across several basic block boundaries.
If static speculation is to be undertaken, then several problems must be solved, one of the most important of which is the handling of exceptional conditions encountered by statically speculated instructions. Hereafter, unless explicitly stated otherwise, references to speculation, speculative instructions, etc. shall be taken to refer to static rather than dynamic speculation.
Since, as noted above, exceptions on speculative instructions cannot be delivered at the time of execution of the instructions, a compiler-visible mechanism is needed to defer the delivery of the exceptions until control is passed to the basic block from which the instructions were speculated (known as the "originating basic block"). Mechanisms that perform a similar function exist in the prior art for deferring and later delivering exceptions on dynamically speculated instructions, however, by definition the mechanisms are not visible to the compiler and therefore cannot be manipulated by the compiler into playing a role in compiler-directed speculation. No known method or apparatus for deferring and later delivering exceptions on statically speculated instructions has been enabled in the prior art. Limited forms of static speculation do exist in the prior art, however: (1) the forms do not involve deferral and later recovery of exceptional conditions, and (2) the forms do not enable static speculation over the breadth and scope of the present invention.
An example of prior art limited static speculation is special case handling of loads from the memory page starting at address zero--called "page zero." In most systems access to page zero is illegal and typically causes a protection violation exception. In certain prior art systems, the compiler and the operating system (OS) mutually agree that any exceptions on loads from page zero are to be suppressed (not deferred) and that, in the event of the suppression, the destination of the load is to be written with zero. This allows the compiler to speculate loads that possess the characteristic that, if they do access illegal memory, they do so only via page zero. The characteristic occurs because the number zero is sometimes used to mark the boundary of data structures and any load going beyond the boundary will therefore attempt to access address zero. It should be noted that the limited form of speculation just described does not involve or allow deferral and later delivery of exceptions and only applies to the narrow class of loads that possess the characteristic of only accessing page zero when illegal. In the event that the load is defined to perform auxiliary operations in addition to reading memory, e.g. adding a value to an address register, then the OS is responsible for emulating the auxiliary operations in software the emulation will reduce program performance.
Another example of prior art limited static speculation is the speculation of instructions that do not cause exceptions. For example, typically the compare instruction is defined such that it does not generate any exceptions. A properly designed compiler may then speculate the compare since the only side effect is the writing of a destination. In the event that control is not passed to the compare's originating basic block, the destination is simply discarded. Another example is a load instruction from an address that is known to be valid at compile time and known to remain constant during runtime, e.g. a global variable. These conditions guarantee that if any exceptions do occur, they will not be fatal and can be handled speculatively without side effects--although the handling of the speculative exceptions may reduce overall performance. Again it should be noted that the limited forms of speculation just described do not involve or allow deferral and only apply to a restricted class of instructions.
Therefore, when undertaking static speculation, there is a need in the art to enable a mechanism to defer exceptions on speculative instructions that applies to as many forms of speculation as possible. The mechanism must posses very low latency otherwise the performance of a program compiled with speculation may actually be lower than the same program compiled without speculation. The mechanism must also place minimal restrictions on the form and the construction of software in order to allow the execution of legacy software, to minimize the impact on software developers, and to maximize the range of software implementation choices. A desired characteristic of The mechanism is to allow the computer system to dynamically adapt to program behavior in order to maximize performance over the broadest possible range of software.